1. Field of the Invention
This invention relates to priority encoding circuits. More particularly, this invention relates to priority encoding circuits within a content addressable memory having a programmable priority index.
2. Description of Related Art
Content addressable memory (CAM) is well known in the art and is employed in applications such as “search engines” in bridge circuits of network routers. A message arrives at the bridge circuit and a destination address is extracted from the message. The address is compared to a database of addresses maintained in a CAM structure. When the address is found within the CAM, the CAM returns an index pointing to the appropriate link leaving the router. The message is then transferred on the link to the next router or the destination. The destination address may in fact match multiple entries within the CAM and for certain addresses or applications it may be desirable for the all the indices to be accessed.
Refer now to FIG. 1 for a discussion of the operation of a CAM of the conventional art. The CAM array 5 is composed of rows of CAM cells 10, which contains the data to be compared against. Each row of CAM cells 10 has an associated compare circuit 15 to simultaneously compare a comparand data 20 to the contents of each row of CAM cells 10. The comparand data 20 is transferred to all the comparators 15 through the bit lines 25 or other comparand lines (not shown) connected to the CAM cells 10 and the comparators 15 of the CAM array 5.
The result from each compare is indicated by the state of each of the match result lines 30. The “match line” passes through the CAM cells of the CAM array 5 along a row. The match lines feed into match line sense amplifiers to produce digital hit or miss indications. Only those match result lines 30 connected to the CAM cells 10 having comparison data matching the comparand data 20 are activated. The match result lines are the inputs to a priority encoder circuit 35. A priority encoder circuit, as is known in the art, provides an output containing a code indicating which of the input lines that are active based on a predetermined priority or precedence. In this circuit, the output lines 40 of the priority encoder 35 provide a Read Only Memory (ROM) address selection dependent on the match result lines 30 having the highest priority or precedence. Traditionally, this would indicate the address having the least magnitude. Obviously, other orders of precedence may be chosen. The output lines 40 of the priority encoder 35 are the address lines for the index ROM 45. The contents of the index ROM 45 are the indices pointing to the locations designated for the corresponding locations of the CAM array 5. The activate output line 40 of the priority encoder 35 causes the contents of the index ROM 45 to be placed at the match index output lines 50 of the index ROM 45. The match index 50 is then transferred to external circuitry for further processing.
The data contents of the rows of CAM cells 10 are written with the data being placed on the bit lines 25 just as the comparand 20 is driven active during a compare operation. The CAM array may include mask cells associated with the CAM cells 10. The mask cells and the associated CAM cells 10 comprise what is referred to as “ternary” CAM cells. A CAM array having only the CAM cells 10 is referred to as a “binary” CAM array. Upon placement of the data on the bit lines 25 or other comparand data lines (not shown), the address 55 is applied to the word line decoder 60. The word line decoder 60 interprets the address 55 to select the word line 65 attached to the row of CAM cells 10 into which the data may be written. If the row of CAM cells 10 includes mask cells, the cells may be masked to create a “don't care” state for those CAM cells.
Attendant with the memory data are flags indicating validity of the data, whether the data is to be ignored in the search, and other information regarding the data. These flags maybe physically part of the rows of memory cells 5 or separate in registers or random access memory (RAM) accessible with either the match lines or with the match index or with associated signals.
The ignore flag is used when all matches in the CAM array 5 to a comparand 20 are to be found. All of the matches for the comparand are identified and the resulting identification location transferred from the CAM array 5 by iteratively searching the CAM array 5. During the first iteration, the match having the highest precedence is identified and the ignore flag is set for the row of CAM cells 10 and a second search is performed and the next match with the next highest precedence is identified, since the match with the highest precedence is ignored. The process is repeated until all the matches within the CAM array 5 are identified. This process requires maintaining a listing of the match indices and from that listing setting the ignore flags and then resetting the ignore flags prior to a subsequent operation that is not a search with the same comparand. In some applications, it maybe desirable to allow searches for the presence of other comparands before determining the other matches for the original comparand. This forces the skip flags to be set and reset depending on which comparand 20 is being applied to the CAM array 5. The setting and resetting of the ignore flags cause extra processing and circuitry to maintain which of the rows of CAM cells 10 are to be ignored during particular searches.
U.S. Pat. No. 6,034,958 (Wicklund) describes an efficient approach to Asynchronous Transfer Mode (ATM) connection table lookup that minimizes the number of tables and memory lookups through the use of hash coding and binary table search techniques. The virtual connection information associated with an incoming ATM cell is hash coded. The hash code provides a compressed representation of the virtual connection information. This allows the address space of a table accessed based on the hash code to be much smaller than the maximum number of possible virtual connection combinations that can be encoded in the ATM cell header without restricting the set of possible virtual connection combinations. A binary search based on the cell's virtual connection information can be used to efficiently select, from plural records accessed based on the hash code, the particular search record corresponding to the cell's connection.